package com.sx.sx1.lintcode.day717;

public class LC904 {


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    static class Solution {
        /**
         * @param head: the first Node
         * @return: the answer after plus one
         */
        public ListNode plusOne(ListNode head) {
            ListNode rnode = reverse(head);
            show(rnode);

            boolean add = true;
            ListNode cur = rnode;
            ListNode last = null;
            while (cur != null) {
                last = cur;
                int v = cur.val;
                if (add) v += 1;

                if (v == 10) {
                    add = true;
                    v = 0;
                } else {
                    add = false;
                }


                cur.val = v;
                cur = cur.next;
            }

            if(add ) last.next= new ListNode(1);


            return reverse(rnode);
        }

        public ListNode reverse(ListNode root) {
            ListNode cur = root;
            ListNode pre = null;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        ListNode n1 = new ListNode(9);
        n1.next = new ListNode(9);
//        n1.next.next = new ListNode(3);

        show(obj.plusOne(n1));

        ListNode n2 = new ListNode(1);
        n2.next = new ListNode(2);
        n2.next.next = new ListNode(3);

        show(obj.plusOne(n2));
    }

    public static void show(ListNode root) {
        ListNode cur = root;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }

        System.out.println();
    }
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
904 · 加一链表
算法
中等
通过率
58%

题目
题解35
笔记
讨论72
排名
记录
描述
给定一个非负整数，这个整数表示为一个非空的单链表，每个节点表示这个整数的一位。返回这个整数加一。

除了0本身，所有数字在最高位前都没有0。

列表的头节点存的是这个整数的最高位。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1

输入: 1 -> 2 -> 3 -> null
输出: 1 -> 2 -> 4 -> null
解释:
123 + 1 = 124
样例2

输入: 9 -> 9 -> null
输出: 1 -> 0 -> 0 -> null
解释:
99 + 1 = 100
标签
企业
Google
相关题目

407
加一
简单
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
13/52
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }

控制台
历史提交

 */
